The packet erasure channel is a communication channel model where transmitted packets are either received or lost, and the location of any lost packet is known. The Internet usually can be modeled as a packet erasure channel. This is because packets transmitted over the Internet can be lost due to corruption or congestion, and the location of any lost packet can be inferred from a sequence number included in a header or payload of each received packet.
Depending on the type of data carried by a stream of packets, a lost packet can reduce the quality of the data or even render the data unusable at a receiver. Therefore, recovery schemes are typically used to provide some level of reliability that packets transmitted over an erasure channel will be received. For example, retransmission schemes are used to recover lost packets in many packet-based networks, but retransmissions can result in long delays when, for example, there is a large distance between the transmitter and receiver or when the channel is heavily impaired. For this reason and others, forward error correction (FEC) using an erasure code is often implemented in place of, or in conjunction with, conventional retransmission schemes.
An erasure code encodes a stream of k packets into a longer stream of n packets such that the original stream of k packets can be recovered at a receiver from a subset of the n packets without the need for any retransmission. The performance of an erasure code can be characterized based on its reception efficiency. The reception efficiency of an erasure code is given by the fraction k′/k, where k′ is the minimum number of the n packets that need to be received in order to recover the original stream of k packets. Certain erasure codes have optimal reception efficiency (i.e., the highest obtainable reception efficiency) and can recover the original stream of k packets using only (and any) k packets out of the n packets transmitted. Such codes are said to be maximum distance separable (MDS) codes.
The Reed-Solomon code is an MDS code with optimal reception efficiency, but the conventional implementation of its encoder/decoder is generally inflexible. Specifically, the conventional Reed-Solomon encoder/decoder has a fixed code rate that cannot be adjusted without first reconstructing the encoder/decoder, which can consume a considerable amount of time and processing power. The code rate is the proportion of an encoded data-stream carrying useful (i.e., non-redundant) information and is given by k/n, where for every k bits of useful information, n total bits are generated, of which n−k bits are redundant.
An encoder with an adjustable code rate is beneficial because the proportion of redundant information generated can be adapted based on the conditions of the erasure channel over which the packets are to be transmitted to improve reliability and/or the data rate. For example, for a bad channel, an adjustable encoder can use a lower code rate to improve reliability, and for a good channel, the adjustable encoder can use a higher code rate to improve the data rate.
The embodiments of the present disclosure will be described with reference to the accompanying drawings. The drawing in which an element first appears is typically indicated by the leftmost digit(s) in the corresponding reference number.